package algorithm.leetcode.I1to100;

import algorithm.leetcode.ListNode;

/**
 * 快慢指针先统计出断点和链表长度
 * 真正旋转的长度为 k % length
 * 执行旋转
 */

public class Q61 {

    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return null;

        ListNode fakeHead = new ListNode(-213);
        fakeHead.next = head;
        ListNode tail = fakeHead, fast = head, slow = head;

        // 找到链表的长度以及真正旋转点位置k
        int length = 0;
        while (tail.next != null) {
            tail = tail.next;
            length++;
        }
        k %= length;
        if (k == 0) return head;

        // 找到旋转点prev的节点
        for (int i = 0; i < k; i++) fast = fast.next;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 执行旋转
        fakeHead.next = slow.next;
        slow.next = null;
        tail.next = head;
        return fakeHead.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;

        Q61 q61 = new Q61();
        System.out.println(q61.rotateRight(listNode1, 200));
    }

}
